package com.ztom.daily.n2022.m6;

/**
 * 火柴拼正方形
 * <p>
 * https://leetcode.cn/problems/matchsticks-to-square/
 *
 * @author ZhangTao
 */
public class Day01Makesquare {

    public boolean makesquare(int[] matchsticks) {
        if (matchsticks == null || matchsticks.length < 4) {
            return false;
        }

        int sum = 0;
        for (int matchstick : matchsticks) {
            sum += matchstick;
        }

        if (sum % 4 != 0) {
            return false;
        }
        quickSort(matchsticks);

        int[] edges = new int[4];
        return dfs(0, matchsticks, edges, sum / 4);
    }

    private boolean dfs(int index, int[] arr, int[] edges, int length) {
        if (index == arr.length) {
            return true;
        }

        for (int i = 0; i < edges.length; i++) {
            edges[i] += arr[index];
            if (edges[i] <= length && dfs(index + 1, arr, edges, length)) {
                return true;
            }
            edges[i] -= arr[index];
        }

        return false;
    }

    public void quickSort(int[] matchsticks) {
        if (matchsticks == null || matchsticks.length == 1) {
            return;
        }
        doQuickSort(matchsticks, 0, matchsticks.length - 1);
    }

    private void doQuickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }

        // 天选之子放到最后
        swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
        int[] mid = netherLandFlag(arr, l, r);
        doQuickSort(arr, l, mid[0]);
        doQuickSort(arr, mid[1], r);
    }

    private int[] netherLandFlag(int[] arr, int l, int r) {
        if (l == r) {
            return new int[]{l, r};
        }

        int num = arr[r];
        int index = l;
        int left = l - 1;
        int right = r;

        while (index < right) {
            if (arr[index] == num) {
                index++;
            } else if (arr[index] > num) {
                swap(arr, ++left, index++);
            } else {
                swap(arr, --right, index);
            }
        }
        swap(arr, r, right);
        return new int[]{left, ++right};
    }

    private void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}
